package jjn.carl.binary_tree;

import commons.TreeNode;

/**
 * @author Jjn
 * @since 2023/7/17 23:39
 */
public class LeetCode654 {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return buildMaxTreeFromArray(nums, 0, nums.length);
    }
    
    private TreeNode buildMaxTreeFromArray(int[] nums, int start, int end) {
        if (end - start < 1) {
            return null;
        }
        if (end - start < 2) {
            return new TreeNode(nums[start]);
        }
        int maxIndex = start;
        int maxNum = nums[start];
        for (int i = start; i < end; i++) {
            if (nums[i] > maxNum) {
                maxIndex = i;
                maxNum = nums[i];
            }
        }
        TreeNode root = new TreeNode(maxNum);
        root.left = buildMaxTreeFromArray(nums, start, maxIndex);
        root.right = buildMaxTreeFromArray(nums, maxIndex + 1, end);
        return root;
    }
    
    public static void main(String[] args) {
        LeetCode654 leetCode654 = new LeetCode654();
        TreeNode node = leetCode654.constructMaximumBinaryTree(new int[]{3, 2, 1, 6, 0, 5});
        System.out.println("node = " + node);
    }
}
